#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void InsertSort(int *a,int n) {
	for (int i = 1; i < n; i++) {
		int key = a[i];
		int j = i - 1;
		for (; j >= 0; j--) {
			if (key < a[j])
				a[j + 1] = a[j];
			else
				break;
		}
		a[j+1] = key;
	}
}
void ShellSort1(int* a, int n) {
	int i = 2;
	while (i < n) {
		int key = a[i];
		int j = i - 2;
		while (j>=0&&a[j] > key)
		{
			a[j + 2] = a[j];
			j -= 2;
		}
		a[j + 2] = key;
		i += 2;
	}
}
void ShellSort2(int* a, int n) {
	int i = 3;
	while (i < n) {
		int key = a[i];
		int j = i - 2;
		while (j >= 0 && a[j] > key)
		{
			a[j + 2] = a[j];
			j -= 2;
		}
		a[j + 2] = key;
		i += 2;
	}
}
void ShellSort(int* a, int n) {
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = gap; i < n; i++) 
		{
			int key = a[i];
			int j = i - gap;
			while (j >= 0 && a[j] > key)
			{
				a[j + gap] = a[j];
				j -= gap;
			}
			a[j + gap] = key;
		}
	}
}
int main() {
	int a[10] = { 7,8,6,9,3,4,5,10,1,2 };
	int n = sizeof(a) / sizeof(a[0]);
	for (int i = 0; i < n; i++) printf("%d ", a[i]);
	printf("\n");
	//ShellSort1(a, n);
	//ShellSort2(a, n);
	ShellSort(a, n);
	for (int i = 0; i < n; i++) printf("%d ", a[i]);
	printf("\n");
	return 0;
}
//int a[10] = {1,5,7,8,9,  2,4,10,3,6};
